package com.zsj.queue;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/3/29 16:12
 * @Description 无序数组实现优先级队列
 */

@SuppressWarnings("all")
public class PriorityQueue<E extends Priority> implements Queue<E> {


    Priority[] priorities;

    int size;

    public PriorityQueue(int capacity) {
        priorities = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) return false;
        priorities[size++] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) return null;
        int max = selectMaxIndex();
        E e = (E) priorities[max];
        remove(max);//删除数组元素
        return e;
    }

    private void remove(int max) {
        //盲猜arraycopy
        if (max < size - 1) {
            //将需要删除的索引元素位置移动给他后面的元素 就完成了元素删除
            //原数组  起始位置 目的数组 目的索引 移动的元素个数
            System.arraycopy(priorities,
                    max + 1, priorities, max, size - 1 - max);
        } else priorities[--size]=null;//gelp gc
    }

    @Override
    public E peek() {
        if (isEmpty()) return null;
        return (E) priorities[selectMaxIndex()];
    }

    private int selectMaxIndex() {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (priorities[i].priority() > priorities[max].priority()) {
                //优先级大
                max = i;
            }
        }
        return max;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == priorities.length;
    }
}
